package algorithm;

import java.util.ArrayList;
import java.util.List;

public class T00051 {
    public static void main(String[] args) {

    }

    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            char[][] arr = new char[n][n];
            for (int i = 0; i < arr.length; i ++) {
                for (int j = 0; j < arr[i].length; j ++) {
                    arr[i][j] = '.';
                }
            }
            List<List<String>> result = new ArrayList<>();
            backTrack(arr, 0, result);
            return result;
        }

        public void backTrack(char[][] arr, int row, List<List<String>> result) {
            if (row == arr.length) {
                recordResult(arr, result);
            }
            for (int j = 0; j < arr[row].length; j ++) {
                if (!isValid(arr, row, j)) continue;
                arr[row][j] = 'Q';
                backTrack(arr, row + 1, result);
                arr[row][j] = '.';
            }
        }

        public boolean isValid(char[][] arr, int row, int col) {
            // 列
            for (int i = 0; i <= row; i ++) {
                if (arr[i][col] == 'Q') return false;
            }
            // 左上
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) {
                if (arr[i][j] == 'Q') return false;
            }
            // 右上
            for (int i = row - 1, j = col + 1; i >= 0 && j < arr.length; i --, j ++) {
                if (arr[i][j] == 'Q') return false;
            }
            return true;
        }

        public void recordResult(char[][] arr, List<List<String>> result) {
            List<String> sl = new ArrayList<>(arr.length);
            for (int i = 0; i < arr.length; i ++) {
                sl.add(new String(arr[i]));
            }
            result.add(sl);
        }
    }
}
